import java.io.File;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;


public class Main {
	public static void main(String[] args) throws Exception { new Main(); }
	int[][] graph;
	int start_node=0;
	int end_node=4;
	
	public Main() throws Exception {
		parse();
		
		while (true) {
			List<Integer> path = dfs(start_node, end_node, new HashSet<Integer>());
			if (path == null) break;
			int local_max=Integer.MAX_VALUE;
			for (int i=0; i+1<path.size(); ++i) {
				local_max = local_max<graph[path.get(i)][path.get(i+1)]? local_max: 
														graph[path.get(i)][path.get(i+1)];
			}
			
			for (int i=0; i+1<path.size(); ++i) {
				int from=path.get(i);
				int to=path.get(i+1);
				graph[from][to] -= local_max;
				graph[to][from] += local_max;
			}
		}
		
		Set<Integer> reach = reachable(start_node, new HashSet<Integer>());
		Set<Edge> mincut = new HashSet<Edge>();
		int maxflow = 0;
		
		for (int i: reach) {
			for (int j=0; j<graph.length; ++j) {
				if (graph[j][i] != 0 && !reach.contains(j)) {
					mincut.add(new Edge(i, j));
					maxflow += graph[j][i]/2;
				}
			}
		}
		System.out.println("mf: "+ maxflow);
		for (Edge e: mincut) {
			System.out.println(e);
		}
	}
	
	private void parse() throws Exception {
		Scanner scan = new Scanner(new File("rail.txt"));
		start_node=0;
		
		int n = Integer.parseInt(scan.next());
		end_node=n-1;
		graph = new int[n][n];
		while (n-- != 0) scan.nextLine();
		scan.nextLine();
		
		n = Integer.parseInt(scan.nextLine());
		while(scan.hasNext()) {
			String[] s = scan.nextLine().split(" ");
			
			int from = Integer.parseInt(s[0]);
			int to = Integer.parseInt(s[1]);
			int cap = Integer.parseInt(s[2]);
			if (cap == -1) cap = Integer.MAX_VALUE;
			
			graph[from][to] = cap;
			graph[to][from] = cap;
		}
	}

	private Set<Integer> reachable(int start, Set<Integer> reach) {
		reach.add(start);
		
		for (int i=0; i<graph[start].length; ++i) {
			if (!reach.contains(i) && (graph[start][i] != 0 || graph[i][start] != 0)) {
				if (graph[start][i] != 0) {
					reach.addAll(reachable(i, reach));
				}
			}
		}
		
		return reach;
	}

	public List<Integer> dfs(int start, int fin, Set<Integer> visited) {
		if (graph[start][fin] != 0) {
			List<Integer> list = new ArrayList<Integer>();
			list.add(start);
			list.add(fin);
			return list;
		}
		visited.add(start);
		
		for (int child=0; child<graph[start].length; ++child) {
			if (graph[start][child] == 0 && graph[child][start] == 0) continue;
			if (graph[start][child] == 0) continue;
			if (visited.contains(child)) continue;
			
			List<Integer> l = dfs(child, fin, visited);
			if (l != null) {
				l.add(0, start);
				return l;
			}
		}
		return null;
	}
	class Edge {
		int start,fin;
		public Edge(int s, int f) {
			start = s;
			fin = f;
		}
		public String toString() {
			return start +" -> "+ fin;
		}
	}
}
